home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / utils / hash / dynahash.c next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  21.8 KB  |  913 lines
  1. /*
  2.  * dynahash.c -- dynamic hashing
  3.  *
  4.  * Identification:
  5.  *    $Header: /private/postgres/src/utils/hash/RCS/dynahash.c,v 1.13 1992/08/18 18:27:16 mer Exp $
  6.  *
  7.  * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  8.  * Coded into C, with minor code improvements, and with hsearch(3) interface,
  9.  * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  10.  * also, hcreate/hdestroy routines added to simulate hsearch(3).
  11.  *
  12.  * These routines simulate hsearch(3) and family, with the important
  13.  * difference that the hash table is dynamic - can grow indefinitely
  14.  * beyond its original size (as supplied to hcreate()).
  15.  *
  16.  * Performance appears to be comparable to that of hsearch(3).
  17.  * The 'source-code' options referred to in hsearch(3)'s 'man' page
  18.  * are not implemented; otherwise functionality is identical.
  19.  *
  20.  * Compilation controls:
  21.  * DEBUG controls some informative traces, mainly for debugging.
  22.  * HASH_STATISTICS causes HashAccesses and HashCollisions to be maintained;
  23.  * when combined with HASH_DEBUG, these are displayed by hdestroy().
  24.  *
  25.  * Problems & fixes to ejp@ausmelb.oz. WARNING: relies on pre-processor
  26.  * concatenation property, in probably unnecessary code 'optimisation'.
  27.  *
  28.  * Modified margo@postgres.berkeley.edu February 1990
  29.  *     added multiple table interface
  30.  * Modified by sullivan@postgres.berkeley.edu April 1990
  31.  *      changed ctl structure for shared memory
  32.  */
  33. /*
  34.     RCS INFO
  35.     $Header: /private/postgres/src/utils/hash/RCS/dynahash.c,v 1.13 1992/08/18 18:27:16 mer Exp $
  36.     $Log: dynahash.c,v $
  37.  * Revision 1.13  1992/08/18  18:27:16  mer
  38.  * allow sequential walk of a hash table (better protocol for hash_seq)
  39.  *
  40.  * Revision 1.12  1992/03/30  00:10:43  mer
  41.  * cut down on calls to hash functions by saving some state
  42.  * .,
  43.  *
  44.  * Revision 1.11  1992/03/05  23:25:29  mer
  45.  * feeble attempt at speed up
  46.  *
  47.  * Revision 1.10  91/11/12  20:20:29  mer
  48.  * prototyping changes
  49.  * 
  50.  * Revision 1.9  1991/09/06  12:30:29  hong
  51.  * added a new function, hash_seq(), which sequentially scans a hash table
  52.  *
  53.  * Revision 1.8  91/08/12  20:54:11  mao
  54.  * make macro name unique
  55.  * 
  56.  * Revision 1.7  1991/08/06  10:44:13  mer
  57.  * fix compile bug
  58.  *
  59.  * Revision 1.6  91/07/31  23:00:03  mer
  60.  * fixes for expanding tables
  61.  * 
  62.  * Revision 1.5  91/07/29  16:54:33  mer
  63.  * cleanup
  64.  * 
  65.  * Revision 1.4  91/04/01  08:49:32  hong
  66.  * for debugging memory leaks.
  67.  * 
  68.  * Revision 1.3  91/03/07  21:56:57  kemnitz
  69.  * Fixed log2() problem.
  70.  * 
  71.  * Revision 1.2  91/01/19  14:31:31  cimarron
  72.  * made some corrections to memory allocation routines --
  73.  * added a DynaHashCxt so that allocations not associated with
  74.  * the caches clutter up the cache context and changed MEM_ALLOC
  75.  * and MEM_FREE macros appropriately.  Note: the old code explicitly
  76.  * allocated things in the CacheCxt but then used pfree() -- this
  77.  * is an error unless you are in the CacheCxt when you call pfree()
  78.  * because it uses the current memory context..  
  79.  * 
  80.  * Revision 1.1  91/01/18  22:32:39  hong
  81.  * Initial revision
  82.  * 
  83.  * Revision 3.1  90/02/23  15:02:24  margo
  84.  * New version -- tests hash interface.  Turns off debug statements but still 
  85.  * collects hash statistics.
  86.  * 
  87.  * Revision 2.1  90/02/23  14:47:25  margo
  88.  * Update revision number to mark completed revision
  89.  * 
  90.  * Revision 1.2  90/02/09  14:21:19  margo
  91.  * My first rev:  multiple tables, user interface allows you to specify own hash
  92.  * function and own table sizes.  Includes both hash and memory hash functions.
  93.  * 
  94. */
  95.  
  96. # include    <stdio.h>
  97. # include    <sys/types.h>
  98. # include    <string.h>
  99. # include    "nodes/mnodes.h"
  100. # include    "tmp/postgres.h"
  101. # include    "utils/hsearch.h"
  102. # include    "utils/mcxt.h"
  103. # include    "utils/log.h"
  104.  
  105. /*
  106.  * Fast arithmetic, relying on powers of 2,
  107.  * and on pre-processor concatenation property
  108.  */
  109.  
  110. # define MOD(x,y)        ((x) & ((y)-1))
  111.  
  112. /*
  113.  * external routines
  114.  */
  115.  
  116. /*
  117.  * Private function prototypes
  118.  */
  119. int *DynaHashAlloc ARGS((unsigned int size ));
  120. void DynaHashFree ARGS((Pointer ptr ));
  121. int hash_clear ARGS((HTAB *hashp ));
  122. uint32 call_hash ARGS((HTAB *hashp , char *k , int len ));
  123. SEG_OFFSET seg_alloc ARGS((HTAB *hashp ));
  124. int bucket_alloc ARGS((HTAB *hashp ));
  125. int my_log2 ARGS((int num ));
  126.  
  127. /* ----------------
  128.  * memory allocation routines
  129.  *
  130.  * for postgres: all hash elements have to be in
  131.  * the global cache context.  Otherwise the postgres
  132.  * garbage collector is going to corrupt them. -wei
  133.  *
  134.  * ??? the "cache" memory context is intended to store only
  135.  *     system cache information.  The user of the hashing
  136.  *     routines should specify which context to use or we
  137.  *     should create a separate memory context for these
  138.  *     hash routines.  For now I have modified this code to
  139.  *     do the latter -cim 1/19/91
  140.  * ----------------
  141.  */
  142. GlobalMemory DynaHashCxt = (GlobalMemory) NULL;
  143.  
  144. int *
  145. DynaHashAlloc(size)
  146.     unsigned int size;
  147. {
  148.     if (! DynaHashCxt)
  149.     DynaHashCxt = CreateGlobalMemory("DynaHash");
  150.  
  151.     return (int *)
  152.     MemoryContextAlloc((MemoryContext)DynaHashCxt, size);
  153. }
  154.  
  155. void
  156. DynaHashFree(ptr)
  157.     Pointer ptr;
  158. {
  159.     MemoryContextFree((MemoryContext)DynaHashCxt, ptr);
  160. }
  161.  
  162. #define MEM_ALLOC    DynaHashAlloc
  163. #define MEM_FREE    DynaHashFree
  164.  
  165. /* ----------------
  166.  * Internal routines
  167.  * ----------------
  168.  */
  169.  
  170. static int expand_table();
  171. static int hdefault();
  172. static int init_htab();
  173.  
  174.  
  175. /*
  176.  * pointer access macros.  Shared memory implementation cannot
  177.  * store pointers in the hash table data structures because 
  178.  * pointer values will be different in different address spaces.
  179.  * these macros convert offsets to pointers and pointers to offsets.
  180.  * Shared memory need not be contiguous, but all addresses must be
  181.  * calculated relative to some offset (segbase).
  182.  */
  183.  
  184. #define GET_SEG(hp,seg_num)\
  185.   (SEGMENT) (((unsigned int) (hp)->segbase) + (hp)->dir[seg_num])
  186.  
  187. #define GET_BUCKET(hp,bucket_offs)\
  188.   (ELEMENT *) (((unsigned int) (hp)->segbase) + bucket_offs)
  189.  
  190. #define MAKE_HASHOFFSET(hp,ptr)\
  191.   ( ((unsigned int) ptr) - ((unsigned int) (hp)->segbase) )
  192.  
  193. # if HASH_STATISTICS
  194. static long hash_accesses, hash_collisions, hash_expansions;
  195. # endif
  196.  
  197. /************************** CREATE ROUTINES **********************/
  198.  
  199. HTAB *
  200. hash_create( nelem, info, flags )
  201. int    nelem;
  202. HASHCTL *info;
  203. int    flags;
  204. {
  205.     register HHDR *    hctl;
  206.     HTAB *         hashp;
  207.     
  208.  
  209.     hashp = (HTAB *) MEM_ALLOC((unsigned int) sizeof(HTAB));
  210.     bzero(hashp,sizeof(HTAB));
  211.  
  212.     if ( flags & HASH_FUNCTION ) {
  213.       hashp->hash    = info->hash;
  214.     } else {
  215.       /* default */
  216.       hashp->hash     = string_hash;
  217.     }
  218.  
  219.     if ( flags & HASH_SHARED_MEM )  {
  220.       /* ctl structure is preallocated for shared memory tables */
  221.  
  222.       hashp->hctl     = (HHDR *) info->hctl;
  223.       hashp->segbase  = (char *) info->segbase; 
  224.       hashp->alloc    = info->alloc;
  225.       hashp->dir       = (SEG_OFFSET *)info->dir;
  226.  
  227.       /* hash table already exists, we're just attaching to it */
  228.       if (flags & HASH_ATTACH) {
  229.         return(hashp);
  230.       }
  231.  
  232.     } else {
  233.       /* setup hash table defaults */
  234.  
  235.       hashp->alloc      = MEM_ALLOC;
  236.       hashp->dir      = NULL;
  237.       hashp->segbase  = NULL;
  238.  
  239.     }
  240.  
  241.     if (! hashp->hctl) {
  242.       hashp->hctl = (HHDR *) hashp->alloc((unsigned int)sizeof(HHDR));
  243.       if (! hashp->hctl) {
  244.         return(0);
  245.       }
  246.     }
  247.       
  248.     if ( !hdefault(hashp) ) return(0);
  249.     hctl = hashp->hctl;
  250. #ifdef HASH_STATISTICS
  251.     hctl->accesses = hctl->collisions = 0;
  252. #endif
  253.  
  254.     if ( flags & HASH_BUCKET )   {
  255.       hctl->bsize   = info->bsize;
  256.       hctl->bshift  = my_log2(info->bsize);
  257.     }
  258.     if ( flags & HASH_SEGMENT )  {
  259.       hctl->ssize   = info->ssize;
  260.       hctl->sshift  = my_log2(info->ssize);
  261.     }
  262.     if ( flags & HASH_FFACTOR )  {
  263.       hctl->ffactor = info->ffactor;
  264.     }
  265.  
  266.     /*
  267.      * SHM hash tables have fixed maximum size (allocate
  268.      * a maximal sized directory).
  269.      */
  270.     if ( flags & HASH_DIRSIZE )  {
  271.       hctl->max_dsize = my_log2(info->max_size);
  272.       hctl->dsize     = my_log2(info->dsize);
  273.     }
  274.     /* hash table now allocates space for key and data
  275.      * but you have to say how much space to allocate 
  276.      */
  277.     if ( flags & HASH_ELEM ) {
  278.       hctl->keysize    = info->keysize; 
  279.       hctl->datasize   = info->datasize;
  280.     }
  281.     if ( flags & HASH_ALLOC )  {
  282.       hashp->alloc = info->alloc;
  283.     }
  284.  
  285.     if ( init_htab (hashp, nelem ) ) {
  286.       hash_destroy(hashp);
  287.       return(0);
  288.     }
  289.     return(hashp);
  290. }
  291.  
  292. /*
  293.     Allocate and initialize an HTAB structure 
  294. */
  295. static int
  296. hdefault(hashp)
  297. HTAB *    hashp;
  298. {
  299.   HHDR    *hctl;
  300.  
  301.   bzero(hashp->hctl,sizeof(HHDR));
  302.  
  303.   hctl = hashp->hctl;
  304.   hctl->bsize    = DEF_BUCKET_SIZE;
  305.   hctl->bshift   = DEF_BUCKET_SHIFT;
  306.   hctl->ssize    = DEF_SEGSIZE;
  307.   hctl->sshift   = DEF_SEGSIZE_SHIFT;
  308.   hctl->dsize    = DEF_DIRSIZE;
  309.   hctl->ffactor  = DEF_FFACTOR;
  310.   hctl->nkeys    = 0;
  311.   hctl->nsegs    = 0;
  312.  
  313.   /* I added these MS. */
  314.  
  315.   /* default memory allocation for hash buckets */
  316.   hctl->keysize     = sizeof(char *);
  317.   hctl->datasize = sizeof(char *);
  318.  
  319.   /* table has no fixed maximum size */
  320.   hctl->max_dsize = NO_MAX_DSIZE;
  321.  
  322.   /* garbage collection for HASH_REMOVE */
  323.   hctl->freeBucketIndex = INVALID_INDEX;
  324.  
  325.   return(1);
  326. }
  327.  
  328.  
  329. static int
  330. init_htab (hashp, nelem )
  331. HTAB *    hashp;
  332. int    nelem;
  333. {
  334.   register SEG_OFFSET    *segp;
  335.   register int nbuckets;
  336.   register int nsegs;
  337.   int    l2;
  338.   HHDR    *hctl;
  339.  
  340.   hctl = hashp->hctl;
  341.  /*
  342.   * Divide number of elements by the fill factor and determine a desired
  343.   * number of buckets.  Allocate space for the next greater power of
  344.   * two number of buckets
  345.   */
  346.   nelem = (nelem - 1) / hctl->ffactor + 1;
  347.  
  348.   l2 = my_log2(nelem);
  349.   nbuckets = 1 << l2;
  350.  
  351.   hctl->max_bucket = hctl->low_mask = nbuckets - 1;
  352.   hctl->high_mask = (nbuckets << 1) - 1;
  353.  
  354.   nsegs = (nbuckets - 1) / hctl->ssize + 1;
  355.   nsegs = 1 << my_log2(nsegs);
  356.  
  357.   if ( nsegs > hctl->dsize ) {
  358.     hctl->dsize  = nsegs;
  359.   }
  360.  
  361.   /* Use two low order bits of points ???? */
  362.   /*
  363.     if ( !(hctl->mem = bit_alloc ( nbuckets )) ) return(-1);
  364.     if ( !(hctl->mod = bit_alloc ( nbuckets )) ) return(-1);
  365.    */
  366.  
  367.   /* allocate a directory */
  368.   if (!(hashp->dir)) {
  369.     hashp->dir = 
  370.       (SEG_OFFSET *)hashp->alloc(hctl->dsize * sizeof(SEG_OFFSET));
  371.     if (! hashp->dir)
  372.       return(-1);
  373.   }
  374.  
  375.   /* Allocate initial segments */
  376.   for (segp = hashp->dir; hctl->nsegs < nsegs; hctl->nsegs++, segp++ ) {
  377.     *segp = seg_alloc(hashp);
  378.     if ( *segp == NULL ) {
  379.       hash_destroy(hashp);
  380.       return (0);
  381.     }
  382.   }
  383.  
  384. # if HASH_DEBUG
  385.   fprintf(stderr, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  386.         "init_htab:",
  387.         "TABLE POINTER   ", hashp,
  388.         "BUCKET SIZE     ", hctl->bsize,
  389.         "BUCKET SHIFT    ", hctl->bshift,
  390.         "DIRECTORY SIZE  ", hctl->dsize,
  391.         "SEGMENT SIZE    ", hctl->ssize,
  392.         "SEGMENT SHIFT   ", hctl->sshift,
  393.         "FILL FACTOR     ", hctl->ffactor,
  394.         "MAX BUCKET      ", hctl->max_bucket,
  395.         "HIGH MASK       ", hctl->high_mask,
  396.         "LOW  MASK       ", hctl->low_mask,
  397.         "NSEGS           ", hctl->nsegs,
  398.         "NKEYS           ", hctl->nkeys );
  399. # endif
  400.     return (0);
  401. }
  402.  
  403. /********************** DESTROY ROUTINES ************************/
  404.  
  405. hash_clear( hashp )
  406. HTAB     *hashp;
  407. {
  408.   elog(NOTICE,"hash_clear not implemented\n");
  409. }
  410.  
  411.  
  412. void
  413. hash_destroy ( hashp )
  414. HTAB    *hashp;
  415. {
  416.   /* cannot destroy a shared memory hash table */
  417.   Assert(! hashp->segbase);
  418.  
  419.   if (hashp != NULL) {
  420.     register SEG_OFFSET     segNum;
  421.     SEGMENT        segp;
  422.     int            nsegs = hashp->hctl->nsegs;
  423.     int         j;
  424.     BUCKET_INDEX    *elp,p,q;
  425.     ELEMENT        *curr;
  426.  
  427.     for (segNum =  0;  nsegs > 0; nsegs--, segNum++) {
  428.  
  429.       segp = GET_SEG(hashp,segNum);
  430.       for (j = 0, elp = segp; j < hashp->hctl->ssize; j++, elp++) {
  431.     for ( p = *elp; p != INVALID_INDEX; p = q ){
  432.       curr = GET_BUCKET(hashp,p);
  433.       q = curr->next;
  434.       MEM_FREE((char *) curr);
  435.     }
  436.       }
  437.       free((char *)segp);
  438.     }
  439.     (void) MEM_FREE( (char *) hashp->dir);
  440.     (void) MEM_FREE( (char *) hashp->hctl);
  441.     hash_stats("destroy",hashp);
  442.     (void) MEM_FREE( (char *) hashp);
  443.   }
  444. }
  445.  
  446. void
  447. hash_stats(where,hashp)
  448. char *where;
  449. HTAB *hashp;
  450. {
  451. # if HASH_STATISTICS
  452.  
  453.     fprintf(stderr,"%s: this HTAB -- accesses %ld collisions %ld\n",
  454.         where,hashp->hctl->accesses,hashp->hctl->collisions);
  455.     
  456.     fprintf(stderr,"hash_stats: keys %ld keysize %ld maxp %d segmentcount %d\n",
  457.         hashp->hctl->nkeys, hashp->hctl->keysize,
  458.         hashp->hctl->max_bucket, hashp->hctl->nsegs);
  459.     fprintf(stderr,"%s: total accesses %ld total collisions %ld\n",
  460.         where, hash_accesses, hash_collisions);
  461.     fprintf(stderr,"hash_stats: total expansions %ld\n",
  462.         hash_expansions);
  463.  
  464. # endif
  465.  
  466. }
  467.  
  468. /*******************************SEARCH ROUTINES *****************************/
  469.  
  470. uint32
  471. call_hash ( hashp, k, len )
  472. HTAB    *hashp;
  473. char    *k;
  474. int     len;
  475. {
  476.         int     hash_val, bucket;
  477.     HHDR    *hctl;
  478.  
  479.     hctl = hashp->hctl;
  480.         hash_val = hashp->hash(k, len);
  481.  
  482.         bucket = hash_val & hctl->high_mask;
  483.         if ( bucket > hctl->max_bucket ) {
  484.             bucket = bucket & hctl->low_mask;
  485.         }
  486.  
  487.         return(bucket);
  488. }
  489.  
  490. /*
  491.  * hash_search -- look up key in table and perform action
  492.  *
  493.  * action is one of HASH_FIND/HASH_ENTER/HASH_REMOVE
  494.  *
  495.  * RETURNS: NULL if table is corrupted, a pointer to the element
  496.  *     found/removed/entered if applicable, TRUE otherwise.
  497.  *    foundPtr is TRUE if we found an element in the table 
  498.  *    (FALSE if we entered one).
  499.  */
  500. int *
  501. hash_search(hashp, keyPtr, action, foundPtr)
  502. HTAB        *hashp;
  503. char        *keyPtr;
  504. HASHACTION    action;        /*
  505.                  * HASH_FIND / HASH_ENTER / HASH_REMOVE
  506.                  * HASH_FIND_SAVE / HASH_REMOVE_SAVED
  507.                  */
  508. Boolean    *foundPtr;
  509. {
  510.     uint32 bucket;
  511.     int segment_num;
  512.     int segment_ndx;
  513.     SEGMENT segp;
  514.     register ELEMENT *curr;
  515.     HHDR    *hctl;
  516.     BUCKET_INDEX    currIndex;
  517.     BUCKET_INDEX    *prevIndexPtr;
  518.     char *        destAddr;
  519.     static struct State {
  520.         ELEMENT      *currElem;
  521.         BUCKET_INDEX currIndex;
  522.         BUCKET_INDEX *prevIndex;
  523.     } saveState;
  524.  
  525.     Assert((hashp && keyPtr));
  526.     Assert((action == HASH_FIND) || (action == HASH_REMOVE) || (action == HASH_ENTER) || (action == HASH_FIND_SAVE) || (action == HASH_REMOVE_SAVED));
  527.  
  528.     hctl = hashp->hctl;
  529.  
  530. # if HASH_STATISTICS
  531.     hash_accesses++;
  532.     hashp->hctl->accesses++;
  533. # endif
  534.     if (action == HASH_REMOVE_SAVED)
  535.     {
  536.         curr = saveState.currElem;
  537.         currIndex = saveState.currIndex;
  538.         prevIndexPtr = saveState.prevIndex;
  539.         /*
  540.          * Try to catch subsequent errors
  541.          */
  542.         Assert(saveState.currElem && !(saveState.currElem = 0));
  543.     }
  544.     else
  545.     {
  546.         bucket = call_hash(hashp, keyPtr, hctl->keysize);
  547.         segment_num = bucket >> hctl->sshift;
  548.         segment_ndx = bucket & ( hctl->ssize - 1 );
  549.  
  550.         segp = GET_SEG(hashp,segment_num);
  551.  
  552.         Assert(segp);
  553.  
  554.         prevIndexPtr = &segp[segment_ndx];
  555.         currIndex = *prevIndexPtr;
  556.  /*
  557.   * Follow collision chain
  558.   */
  559.         for (curr = NULL;currIndex != INVALID_INDEX;) {
  560.       /* coerce bucket index into a pointer */
  561.           curr = GET_BUCKET(hashp,currIndex);
  562.  
  563.           if (! bcmp((char *)&(curr->key), keyPtr, hctl->keysize)) {
  564.             break;
  565.           } 
  566.           prevIndexPtr = &(curr->next);
  567.           currIndex = *prevIndexPtr;
  568. # if HASH_STATISTICS
  569.           hash_collisions++;
  570.           hashp->hctl->collisions++;
  571. # endif
  572.         }
  573.     }
  574.  
  575.     /*
  576.      *  if we found an entry or if we weren't trying
  577.      * to insert, we're done now.
  578.      */
  579.     *foundPtr = (Boolean) (currIndex != INVALID_INDEX);
  580.     switch (action) {
  581.     case HASH_ENTER:
  582.       if (currIndex != INVALID_INDEX)
  583.         return(&(curr->key));
  584.       break;
  585.     case HASH_REMOVE:
  586.     case HASH_REMOVE_SAVED:
  587.       if (currIndex != INVALID_INDEX) {
  588.         Assert(hctl->nkeys > 0);
  589.         hctl->nkeys--;
  590.  
  591.         /* add the bucket to the freelist for this table.  */
  592.         *prevIndexPtr = curr->next;
  593.         curr->next = hctl->freeBucketIndex;
  594.         hctl->freeBucketIndex = currIndex;
  595.  
  596.         /* better hope the caller is synchronizing access to
  597.          * this element, because someone else is going to reuse
  598.          * it the next time something is added to the table
  599.          */
  600.         return (&(curr->key));
  601.       }
  602.       return((int *) TRUE);
  603.     case HASH_FIND:
  604.       if (currIndex != INVALID_INDEX)
  605.         return(&(curr->key));
  606.       return((int *)TRUE);
  607.     case HASH_FIND_SAVE:
  608.       if (currIndex != INVALID_INDEX)
  609.       {
  610.           saveState.currElem = curr;
  611.           saveState.prevIndex = prevIndexPtr;
  612.           saveState.currIndex = currIndex;
  613.           return(&(curr->key));
  614.       }
  615.       return((int *)TRUE);
  616.     default:
  617.       /* can't get here */
  618.       return (NULL);
  619.     }
  620.  
  621.     /* 
  622.         If we got here, then we didn't find the element and
  623.         we have to insert it into the hash table
  624.     */
  625.     Assert(currIndex == INVALID_INDEX);
  626.  
  627.     /* get the next free bucket */
  628.     currIndex = hctl->freeBucketIndex;
  629.     if (currIndex == INVALID_INDEX) {
  630.  
  631.       /* no free elements.  allocate another chunk of buckets */
  632.       if (! bucket_alloc(hashp)) {
  633.         return(NULL);
  634.       }
  635.       currIndex = hctl->freeBucketIndex;
  636.     }
  637.     Assert(currIndex != INVALID_INDEX);
  638.  
  639.     curr = GET_BUCKET(hashp,currIndex);
  640.     hctl->freeBucketIndex = curr->next;
  641.  
  642.       /* link into chain */
  643.     *prevIndexPtr = currIndex;    
  644.  
  645.       /* copy key and data */
  646.     destAddr = (char *) &(curr->key);
  647.     bcopy(keyPtr,destAddr,hctl->keysize);
  648.     curr->next = INVALID_INDEX;
  649.  
  650.     /* let the caller initialize the data field after 
  651.      * hash_search returns.
  652.      */
  653. /*    bcopy(keyPtr,destAddr,hctl->keysize+hctl->datasize);*/
  654.  
  655.         /*
  656.          * Check if it is time to split the segment
  657.          */
  658.     if (++hctl->nkeys / (hctl->max_bucket+1) > hctl->ffactor) {
  659. /*
  660.       fprintf(stderr,"expanding on '%s'\n",keyPtr);
  661.       hash_stats("expanded table",hashp);
  662. */
  663.       if (! expand_table(hashp))
  664.         return(NULL);
  665.     }
  666.     return (&(curr->key));
  667. }
  668.  
  669. /*
  670.  * hash_seq -- sequentially search through hash table and return
  671.  *             all the elements one by one, return NULL on error and
  672.  *           return TRUE in the end.
  673.  *
  674.  */
  675. int *
  676. hash_seq(hashp)
  677. HTAB        *hashp;
  678. {
  679.     static uint32 curBucket = 0;
  680.     static ELEMENT *curElem = NULL;
  681.     int segment_num;
  682.     int segment_ndx;
  683.     SEGMENT segp;
  684.     HHDR *hctl;
  685.     BUCKET_INDEX currIndex;
  686.     BUCKET_INDEX *prevIndexPtr;
  687.     char *destAddr;
  688.  
  689.     if (hashp == NULL)
  690.     {
  691.     /*
  692.      * reset static state
  693.      */
  694.     curBucket = 0;
  695.     curElem = NULL;
  696.     return NULL;
  697.     }
  698.  
  699.     hctl = hashp->hctl;
  700.     for (; curBucket <= hctl->max_bucket; curBucket++) {
  701.     segment_num = curBucket >> hctl->sshift;
  702.     segment_ndx = curBucket & ( hctl->ssize - 1 );
  703.  
  704.     segp = GET_SEG(hashp, segment_num);
  705.  
  706.     if (segp == NULL)
  707.         return NULL;
  708.     if (curElem == NULL)
  709.         prevIndexPtr = &segp[segment_ndx];
  710.     else
  711.         prevIndexPtr = &(curElem->next);
  712.     currIndex = *prevIndexPtr;
  713.     if (currIndex == INVALID_INDEX) {
  714.         curElem = NULL;
  715.         continue;
  716.       }
  717.     curElem = GET_BUCKET(hashp, currIndex);
  718.     return(&(curElem->key));
  719.       }
  720.     return (int*)TRUE;
  721. }
  722.  
  723.  
  724. /********************************* UTILITIES ************************/
  725. static int
  726. expand_table(hashp)
  727. HTAB *    hashp;
  728. {
  729.       HHDR    *hctl;
  730.     SEGMENT    old_seg,new_seg;
  731.     int    old_bucket, new_bucket;
  732.     int    new_segnum, new_segndx;
  733.     int    old_segnum, old_segndx;
  734.     int    dirsize;
  735.     ELEMENT    *chain;
  736.     BUCKET_INDEX *old,*newbi;
  737.     register BUCKET_INDEX chainIndex,nextIndex;
  738.  
  739. #ifdef HASH_STATISTICS
  740.     hash_expansions++;
  741. #endif
  742.  
  743.     hctl = hashp->hctl;
  744.     new_bucket = ++hctl->max_bucket;
  745.     old_bucket = (hctl->max_bucket & hctl->low_mask);
  746.  
  747.     new_segnum = new_bucket >> hctl->sshift;
  748.     new_segndx = MOD ( new_bucket, hctl->ssize );
  749.  
  750.     if ( new_segnum >= hctl->nsegs ) {
  751.       
  752.       /* Allocate new segment if necessary */
  753.       if (new_segnum >= hctl->dsize) {
  754.         (void) dir_realloc(hashp);
  755.       }
  756.       if (! (hashp->dir[new_segnum] = seg_alloc(hashp))) {
  757.         return (0);
  758.       }
  759.       hctl->nsegs++;
  760.     }
  761.  
  762.  
  763.     if ( new_bucket > hctl->high_mask ) {
  764.         /* Starting a new doubling */
  765.         hctl->low_mask = hctl->high_mask;
  766.         hctl->high_mask = new_bucket | hctl->low_mask;
  767.     }
  768.  
  769.     /*
  770.      * Relocate records to the new bucket
  771.      */
  772.     old_segnum = old_bucket >> hctl->sshift;
  773.     old_segndx = MOD(old_bucket, hctl->ssize);
  774.  
  775.         old_seg = GET_SEG(hashp,old_segnum);
  776.         new_seg = GET_SEG(hashp,new_segnum);
  777.  
  778.     old = &old_seg[old_segndx];
  779.     newbi = &new_seg[new_segndx];
  780.     for (chainIndex = *old; 
  781.          chainIndex != INVALID_INDEX;
  782.          chainIndex = nextIndex){
  783.  
  784.       chain = GET_BUCKET(hashp,chainIndex);
  785.       nextIndex = chain->next;
  786.       if ( call_hash(hashp,
  787.              (char *)&(chain->key),
  788.              hctl->keysize) == old_bucket ) {
  789.         *old = chainIndex;
  790.         old = &chain->next;
  791.       } else {
  792.         *newbi = chainIndex;
  793.         newbi = &chain->next;
  794.       }
  795.         chain->next = INVALID_INDEX;
  796.     }
  797.     return (1);
  798. }
  799.  
  800.  
  801. static int
  802. dir_realloc ( hashp )
  803. HTAB *    hashp;
  804. {
  805.     register char    *p;
  806.     char    **p_ptr;
  807.     int    old_dirsize;
  808.     int    new_dirsize;
  809.  
  810.  
  811.     if (hashp->hctl->max_dsize != NO_MAX_DSIZE) 
  812.       return (0);
  813.  
  814.     /* Reallocate directory */
  815.     old_dirsize = hashp->hctl->dsize * sizeof ( SEGMENT * );
  816.     new_dirsize = old_dirsize << 1;
  817.  
  818.     p_ptr = (char **) hashp->dir;
  819.     p = (char *) hashp->alloc((unsigned int) new_dirsize );
  820.     if (p != NULL) {
  821.       bcopy ( *p_ptr, p, old_dirsize );
  822.       bzero ( *p_ptr + old_dirsize, new_dirsize-old_dirsize );
  823.       (void) free( (char *)*p_ptr);
  824.       *p_ptr = p;
  825.       hashp->hctl->dsize = new_dirsize;
  826.       return(1);
  827.     } 
  828.     return (0);
  829.  
  830. }
  831.  
  832.  
  833. SEG_OFFSET
  834. seg_alloc(hashp)
  835. HTAB * hashp;
  836. {
  837.   SEGMENT segp;
  838.   SEG_OFFSET segOffset;
  839.   
  840.  
  841.   segp = (SEGMENT) hashp->alloc((unsigned int) 
  842.         sizeof(SEGMENT)*hashp->hctl->ssize);
  843.  
  844.   if (! segp) {
  845.     return(0);
  846.   }
  847.  
  848.   bzero((char *)segp,
  849.     (int) sizeof(SEGMENT)*hashp->hctl->ssize);
  850.  
  851.   segOffset = MAKE_HASHOFFSET(hashp,segp);
  852.   return(segOffset);
  853. }
  854.  
  855. /*
  856.  * allocate some new buckets and link them into the free list
  857.  */
  858. bucket_alloc(hashp)
  859. HTAB *hashp;
  860. {
  861.   int i;
  862.   ELEMENT *tmpBucket;
  863.   int bucketSize;
  864.   BUCKET_INDEX tmpIndex,lastIndex;
  865.  
  866.   bucketSize = 
  867.     sizeof(BUCKET_INDEX) + hashp->hctl->keysize + hashp->hctl->datasize;
  868.  
  869.   /* make sure its aligned correctly */
  870.   bucketSize += sizeof(int *) - (bucketSize % sizeof(int *));
  871.  
  872.   /* tmpIndex is the shmem offset into the first bucket of
  873.    * the array.
  874.    */
  875.   tmpBucket = (ELEMENT *)
  876.     hashp->alloc((unsigned int) BUCKET_ALLOC_INCR*bucketSize);
  877.  
  878.   if (! tmpBucket) {
  879.     return(0);
  880.   }
  881.  
  882.   tmpIndex = MAKE_HASHOFFSET(hashp,tmpBucket);
  883.  
  884.   /* set the freebucket list to point to the first bucket */
  885.   lastIndex = hashp->hctl->freeBucketIndex;
  886.   hashp->hctl->freeBucketIndex = tmpIndex;
  887.  
  888.   /* initialize each bucket to point to the one behind it */
  889.   for (i=0;i<(BUCKET_ALLOC_INCR-1);i++) {
  890.     tmpBucket = GET_BUCKET(hashp,tmpIndex);
  891.     tmpIndex += bucketSize;
  892.     tmpBucket->next = tmpIndex;
  893.   }
  894.   
  895.   /* the last bucket points to the old freelist head (which is
  896.    * probably invalid or we wouldnt be here) 
  897.    */
  898.   tmpBucket->next = lastIndex;
  899.  
  900.   return(1);
  901. }
  902.  
  903. /* calculate the log base 2 of num */
  904. my_log2( num )
  905. int    num;
  906. {
  907.     int        i = 1;
  908.     int        limit;
  909.  
  910.     for ( i = 0, limit = 1; limit < num; limit = 2 * limit, i++ );
  911.     return (i);
  912. }
  913.